import java.io.*;
import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val=x;
        next=null;
    }
}

public class MergeTwoSortedLists {
    public static ListNode mergeTwoLists(ListNode l1,ListNode l2) {
        if(l1==null) return l1;
        if(l2==null) return l2;

        ListNode p1 = l1;
        ListNode p2 = l2;

        ListNode p3 = null;

        if(p1.val < p2.val){
            p3 = p1;
            p1 = p1.next;
        }
        else{
            p3 = p2;
            p2 = p2.next;
        }

        ListNode pHead = p3;
        
        while(p1!=null && p2!=null){
            if(p1.val < p2.val) {
                p3.next = p1;
                p1 = p1.next;
                p3 = p3.next;
            }
            else {
                p3.next = p2;
                p2 = p2.next;
                p3 = p3.next;
            }
        }

        if(p1 != null) {
            p3.next = p1;
        }

        if(p2 != null) {
            p3.next = p2;
        }

        return pHead;
    }
    
    public static void main(String[] args) {
                ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        ListNode l1 = new ListNode(0);
        ListNode l2 = new ListNode(0);        
        ListNode pHead1 = l1;
        ListNode pHead2 = l2;        
        
        for(int i=0;i<list.size();i++){
            ListNode p1 = new ListNode(list.get(i));
            pHead1.next = p1;
            pHead1 = p1;

            if(i<=10) {
                ListNode p2 = new ListNode(list.get(i));                        
                pHead2.next = p2;
                pHead2 = p2;
            }
        }
        printListNode(l1);
        System.out.println("==============================");
        printListNode(l2);
        System.out.println("==============================");
        
        printListNode(mergeTwoLists(l1,l2));
    }

    public static void printListNode(ListNode listNode) {
        while(listNode!=null){
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

}